I. INTRODUCTION:

With the advance of wireless communication technology, portable computers with radios are being increasingly deployed in common activities. Applications such as conferences, meetings, lectures, crowd control, search and rescue, disaster recovery, and automated battlefields typically do not have central administration or infrastructure available. In these situations, ad hoc networks, or packet radio networks [8 consisting of hosts equipped with portable radios must be deployed impromptu without any wired base stations. In ad hoc networks, each host must act as a router since routes are mostly multichip. Nodes in such a net- work move arbitrarily, thus network topology changes frequently, unpredictably, and may consist of unidirectional links as well as bidirectional links. Moreover,

wireless channel bandwidth is limited. The scarce bandwidth decreases even further due to the effects of multiple access, signal interference, and channel fading. Network hosts of ad hoc networks operate on constrained battery power which will eventually be exhausted. Ad hoc networks are also more prone to security threats. All these limitations and constraints make multichip network research more challenging.

II. OVERVIEW OF THE ROUTING PROTOCOL:

The routing protocol utilized for the scalability study is the Ad hoc On-Demand Distance Vector (AODV) protocol [128, 139]. AODV is an on-demand protocol which is capable of providing unicast, multicast, and broadcast communication. For the purposes of this study, its unicast operation is focused upon. Route discovery is based on a route request/route reply query cycle. Once discovered, a route is maintained as long as needed by the source. To guarantee loop freedom, AODV utilizes per node sequence numbers. A node increment the value of its Route Discovery Route discovery begins when a source node needs a route to some destination. It places the destination IP address and last known sequence number for that destination, as well as its own IP address and current sequence number, into a Route Request (RREQ). It then broadcasts the RREQ and sets a timer to wait for a reply.

When a node receives the RREQ, it first creates a reverse route entry for the source node in its route table. It then checks whether it has an unexpired route to the destination node. In order to respond to the RREQ, the node must either

be the destination itself, or it must have an unexpired route to the destination whose corresponding sequence number is at least as great as that contained in the RREQ. If neither of these conditions is met, the node rebroadcasts the RREQ.

On the other hand, if it does meet either of these conditions, the node then creates a Route Reply (RREP) message. It places the current sequence number of the destination, as well as its distance in hops to the destination, into the RREP, and then unicasts this message back to the source. The node from which it received the RREQ is used as the next hop. When an intermediate node receives the RREP, it creates a forward route entry for the destination node in its route table, and then forwards the RREP to the source node. Once the source node receives the RREP, it can begin using the route to transmit data packets to the destination. If it later receives a RREP with a greater destination sequence number or equivalent sequence number and smaller hop count, it updates its route table entry and begins using the new route.

If the source node does not receive a RREP by the time its discovery timer expires, it rebroadcasts the RREQ. It attempts discovery up to some maximum number of times. If no route is discovered after the maximum number of attempts sequence number whenever there is a change in its local connectivity information Route Maintenance An active route is defined as a route which has recently been used to transmit data packets. Link breaks in non-active links do not trigger any protocol action. However, when a link break in an active route occurs, the node upstream of the break determines whether any of its neighbors use that link to reach the destination. If so, it creates a Route Error (RERR) packet. The RERR contains the IP address of each destination which is now unreachable, due to the link break. The RERR also contains the sequence number of each such destination, incremented by one. The node then broadcasts the packet and invalidates those routes in its route table.

When a neighboring node receives the RERR, it in turn invalidates each of the routes listed in the packet, if that route used the source of the RERR as a next hop. If one or more routes is deleted, it then goes through the same process, whereby it checks whether any of its neighbors route through it to reach the destinations. If so, it creates and broadcasts its own RERR message. Once a source node receives the RERR, it invalidates the listed routes as described. If it determines it still needs any of the expired routes, it then re- initiates route discovery for that route.

The QoS multicast routing protocols present in the current scenario were also reviewed along with the also operations A comparative study for wired, mobile ad hoc and QoS routing protocols were also made. The multicast paradigm consists of group management protocols, routing protocols and transport protocols The group management protocols are used to report the group membership state information of the hosts to the multicast routers. Multicast routing protocols are aimed to efficiently route the multicast packets by intuitively constructing a tree structure [14] Interestingly, many multicast applications require beyond the best effort delivery provided by multicast routing protocols and hence various multicast transport protocols are proposed on top of the multicast outing protocols to meet the needs of different applications In multicast routing, the main issue 1s to construct a multicast tree where in all the members of the multicast group are the nodes of the tree. The multicast tree 1s mathematically defined as follows Consider a network graph G (Y, E), where V is set of nodes and E 1s set of edges In graph G Let Rs denote the set of multicast receivers, s the multicast source node and c(u,v) the cost of edge (u,v) The objective is to find the minimum cost multicast tree The function may be stated as follows

III. TAXONOMY OF MULTICAST ROUTING PROTOCOLS:

There are various Issues on which the multicast routing protocols are classified into different categories. For instance, they can be classified by how multicast connectivity 1s established and maintained, namely, source-imitated and receiver initiated a source initiated approach, the formation of the multicast group IS initiated by the source and a tree or mesh IS constructed per sender The source polls the network periodically with join-request packets Receivers willing to join the multicast group respond with m-reply packets after receiving the request.

In a receiver-initiated approach, a receiver floods a join request packet to search for a path to a multicast group One common technique used with this approach is to assign a node, known as the Rendezvous Point (RP) or the core, to accept join requests from members The multicast connection then consists of the shortest paths from the core to each of the members The multicast routing protocol can be either proactive or reactive based on their operation type Proactive protocols typically require table-driven preparation activities, whereas m reactive protocols the process IS on-demand It IS also understood that, on-demand approaches for constructing the tree or mesh are always best suited than the table driven ones due to the dynamic variations in the topology of mobile ad hoc networks. Finally, multicast routing protocols are classified into tree-based and mesh based protocols based on the topology.[5] In tree-based protocols, there exists only one possible path between a source-destination pair, whereas In mesh-based protocols, there may exist more than one path.

Figure 1 : (a) Shortest path trees and (b) Shared trees

The tree based protocols are further classified Into source-based shortest path tree and shared tree [15] as ~llustrated1 x1 Figure 1 For figure 1 (a), two sources, SI and S2, use the shortest paths to reach their host subnets But, In Figure 2 1 @), the sources send their data first to the core of their shared tree The common core then distributes the data packets to third estimations As source-based trees use the shortest path for minimum delay, these structures are appropriate for regions where group members are densely distributed[6] On the other hand, shared trees have better resource utilization source-based trees, while increasing the traffic concentration While tree based protocols are more efficient In terms of resource usage, mesh-based protocols are more robust to the changes 1n the network However, the classification of existing multicast routing protocols both in wired and wireless networks have been broadly classified based on the topology into source tree, shared tree and mesh protocols This has been depicted in the Figure 2

Figure 2 Classification of multicast routing protocols

IV. MULTICASTING IN WIRED NETWORKS:

Distance Vector Multicast Routing Protocol (DVMRP) DVMRP [7] is a source-based multicast routing protocol which makes use of the distance vector algorithm to prepare routing information DVMRP uses Reverse Path Multicar (RPM) method to construct the multicast tree. It is basically a broadcast-and-prune method wherein, on arrival of a packet from a source nodes, a router forwards the packet to all other nodes only if the packet arrives on the shortest path from the sources This has been shown in the Figure 3 (a) and @) If there are no receivers attached to any leaf router In its sub-network, then 11 sends prune message back to the source In order to detach itself from the multicast tree and the resultant rnultlcast tree 1s constructed as m Figure 3 (c) and (d)

Figure 3 : DVMRP operations: (a) The Source and the members, @) Forwarding of packets, (c) Prune messages hack to the source to detach and (d) The resultant multicast tree

The DVMRP router maintains a forwarding table to keep the incoming and outgoing Interfaces and updates the table accordingly The forwarding process of the packets and timing of branches based on prune messages 1s repeated periodically to keep the tree update DVMRP also implements a mechanism to quickly get back a previously pruned branch of a tree, lf a router that previously sent a prune message discovers new group members on network This grafting mechanism reduces the join latency DVMRP operates Independent of unicast routing It maintains 11s own unicast information through exchange of distance vectors with multicast capable neighbors.[2]

Multicast Open Shortest Path First Protocol (MOSPF)

by flooding a Link State Advertisement (LSAj, called The MOSPF IS a source-based protocol which 1s the multicast version of the 11nk state routing protocol [38, 391 In MOSPF, each router has the whole network and membership information group membership LSA Routers advertise the11 local state information to the network periodically and each router collects this information In a Link-state database Upon the arrival of the first data packet for a group, each router builds the shortest path tree rooted at the sender using Dykstra's algorithm The MSOPF routers use the Internet Group Management Protocol (IGMP) [44], to maintain the multicast group membership information using group membership LSA to other routers Using this group information the tree IS constructed, the routers maintain the tree information forwarding table for future usage [13,15] The forwarding table 1s updated only if the multicast group or the network topology changes.

Protocol Independent Multicast (PIM)

PIM 1s set of on-demand routing protocols developed by the Inter-Doman Multicast Routing (IDMR) working group of the IETF with an objective of providing scalable multicast routing across the Internet PIM has two variations namely, Path Dense-Mode (PIM-DM) [10] and PIM Sparse-Mode (PIM-SM) [3]PIM-DM 1s source-based and PIM-SM 1s core-based multicast routing protocols Dense-mode protocol refers to an environment where group members are relatively densely distributed In the network and bandwidth 1s plentiful while sparse-mode protocol refer to the environments where group members are distributed across many reasons of the Internet and bandwidth s not necessarily widely available It 1s important to note that sparse-mode does not imply that the group has a few members, just that they are widely dispersed across the Internet As these protocols do not dependent on any particular unicast routing protocol, they receive the name PIM However, any implementation supporting PIM requires the presence of a unicast routing protocol to provide routing table information and to adapt to the change In topology PIM makes a clear distinction between a multicast routing protocol that is designed for dense and sparse environments

PIM-DM: PIM-DM builds source-based multicast trees by using RPM mechanism similar to DVMW Thus, PIM-DM is also a data driven protocol that floods packets to the edges and expects prune messages from inactive branches A minor difference from DVMRP is that PIM-DM floods packets for any new (source. group) pairs on all non incoming interfaces and it requires the presence of a unicast routing protocol to provide routing and topology change information PIM-DM.[4] Pruning ~n PIM-DM happens only through explicit prune messages, from routers which do not have any group embers finally, PIM-DM uses a reliable graft mechanism to disable previously-sent prune requests when new downstream group members appear after, a prune has been sent Since PIM-DM uses RPM, it implements a reverse-path check on all packets to verify that the received packets amve on the Interface that the router would use ~f it needed to send a packet toward the source Since PIM-DM does not have ~ tows n muting protocol, it uses the existing unicast routing protocol to locate itself with respect to the source of multicast packets[1]

PIM-SM: PIM-SM use both source-based and core-based trees for multicasting By default, ~t uses core-based trees rooted at the RP, but regardless of which tree type IS In use In PIM-SM, new receivers Issues PIM-Jom messages through that local PIM-SM router using lGMP toward the RP to directly attach to the core The local router then creates a forwarding table for the new receiver with the group and explicitly ln the distribution tree by sending a unicast PIM-join message to the group's RP These join messages establish forwarding state In the ln termed after outers which 1s used In the future to make forwarding decisions As each packet 1s received, ~t must match a pre-existing forwarding cache entry This 1s consistent with the forwarding technique used by PLM-DM and smaller to that used by DVMRP The unicast routing table provides the necessary information to determine the best route towards the group's RP, the packet must have arrived on the Interface this router would use to send traffic toward the group's RP Note that the forwarding state, which IS created by PIM-SM, 1s unidirectional. When a data source first sends to a group, its local router unicast PIM Register- Message to the RP with the source's data packet encapsulated within the member join process 1s shown In the Figure 4

Figure 4 Member join process in PIM-SM

V. ROUTING STRATEGIES:

Dense mode: Dense mode multicast is one mode that multicast can use to construct a tree for sending packets to the multicast sub scribers[8]. It is the opposite of sparse multicast. Dense mode is ideal for groups where many of the nodes will subscribe to receive the multicast packets, so that most of the routers must receive and forward these packets (groups of a high density). The source initially broadcasts to every router, and thus every node. Then each node that does not wish to receive packets destined for that group will send a prune message to its router. Upon receiving a prune message, the router will modify its state so that it will not forward those packets out that interface. If every interface on a router is pruned, the router will also be pruned.[9]

Multicast Forwarding with Dense Mode

· Dense-mode protocols assume that every subnet contains at least one recipient of any multicast group for which it might see a packet. “Flooding” is the operative word here. Build an ark, people - dense-mode routing protocol in full-effect.

· Dense-mode protocols tell the router to forward multicast traffic out every interface, except when this could cause a loop. Multicast packets aren’t forwarded out the interface they came in on, for instance.

· Dense-mode protocols allow the router to opt-out of certain multicast groups via a “prune” message. The router may want to do this if the following is true:

o There are no downstream routers who need those multicast packets.

o There are no hosts on connected subnets who need those multicast packets.

· DVMRP, PIM-DM and MOSPF are dense-mode routing protocols.

Figure 5 : Dense Mode Multicast

Description of the picture:

(1), perhaps the router E chooses B as its RPF neighbor, based on unicast routing back to the source. Then E receives a multicast packet on the point-to-point interface from C. It sends a rate-limited Prune to C.

(2), the routers E and F on the LAN exchange Assert packets, when E or F sees the multicast forwarded by the other of the two. Suppose E wins, based on unicast routing metric or address. Then F knows not to forward multicasts on the LAN. Note that G and H are not involved, since the Ethernet is their RPF interface.

(3), suppose router G has no receivers downstream. It can then send a LAN Prune to the Forwarder for the LAN, router E.

(4), if router H has local or downstream receiver(s), it counters this with a LAN Join.

(5), suppose router D had no downstream or local receivers and sent a Prune to B. Suppose sometime later on of the PC's to its right sends it an IGMP message for the same multicast group. Router D can then send a PIM Graft to B, asking B to resume sending it the specified multicast group.

Center Mode: is a protocol for efficiently routing Internet Protocol (IP) packets to multicast groups that may span wide-area and inter-domain internets[4]. The protocol is named protocol-independent because it is not dependent on any particular unicast routing protocol for topology discovery, and sparse-mode because it is suitable for groups where a very low percentage of the nodes (and their routers) will subscribe to the multicast session. Unlike earlier dense-mode multicast routing protocols such as DVMRP and dense multicast routing which flooded packets across the network and then pruned off branches where there were no receivers, PIM-SM explicitly constructs a tree from each sender to the receivers in the multicast group[12].

Multi-cast clients

A router receives explicit Join/Prune messages from those neighboring routers that have downstream group members.

· In order to join a multi-cast group, G, a host conveys its membership information through the Internet Group Management Protocol (IGMP).

· The router then forwards data packets addressed to a multi-cast group G to only those interfaces on which explicit joins have been received.

· A Designated Router (DR) sends periodic Join/Prune messages toward a group-specific Rendezvous Point (RP) for each group for which it has active members.

o Note that one router will be automatically or statically designated as the rendezvous point (RP), and all routers must explicitly join through the RP.

· Each router along the path toward the RP builds a wild card (any-source) state for the group and sends Join/Prune messages on toward the RP.

o The term route entry is used to refer to the state maintained in a router to represent the distribution tree.

o A route entry may include such fields as:

§ source address

§ the group address

§ the incoming interface from which packets are accepted

§ the list of outgoing interfaces to which packets are sent

§ timers, flag bits, etc.

o The wild card route entry's incoming interface points toward the RP

o The outgoing interfaces point to the neighboring downstream routers that have sent Join/Prune messages toward the RP.

· This state creates a shared, RP-centered, distribution tree that reaches all group members.

Multi-cast sources

· When a data source first sends to a group, its Designated Router (DR) uni-casts Register messages to the Rendezvous Point (RP) with the source's data packets encapsulated within.

· If the data rate is high, the RP can send source-specific Join/Prune messages back towards the source and the source's data packets will follow the resulting forwarding state and travel un-encapsulated to the RP.

· Whether they arrive encapsulated or natively, the RP forwards the source's de-capsulated data packets down the RP-centered distribution tree toward group members.

· If the data rate warrants it, routers with local receivers can join a source-specific, shortest path, distribution tree, and prune this source's packets off the shared RP-centered tree.

· For low data rate sources, neither the RP, nor last-hop routers need join a source-specific shortest path tree and data packets can be delivered via the shared RP-tree. Once the other routers which need to receive those group packets have subscribed, the RP will unsubscribe to that multi-cast group, unless it also needs to forward packets to another router or node. Additionally, the routers will use reverse-path forwarding to ensure that there are no loops for packet forwarding among routers that wish to receive multi-cast packets.

VI EXPERIMENTAL RESULTS:

Figure 1 : Data Transmission using Center Mode.

Figure 2 : Data Transmission using Dense Mode.

Figure 3 : Performance of Network using Center Mode.

Figure 4 : Performance of Network using Dense Mode.

Figure 5 : Throughput of Network using center Mode.

Figure 6 : Throughput of Network using Dense Mode.

VII. CONCLUSION:

Wireless mobile ad hoc networks present difficult challenges to routing and multicasting protocol designers. Mobility, constrained bandwidth, and limited power cause frequent topology changes. Routing protocols must construct and maintain multihop routes in dynamic ad hoc networks effectively and efficiently. We studied various routing and multicasting approaches in this dissertation. The main lesson learned from our studies is that on-demand protocols are well suited for mobile ad hoc networks, especially when the mobility rate is high. Efficient utilization of control packets is the primary reason of good performances. Pro- viding alternate and multiple routes proved to be beneficial because they increase robustness to mobility and fading.

VIII. REFERENCES:

[1] A. Acharya and B.R. Badrinath, \A Framework for Delivering Multicast Messages in Networks with Mobile Hosts," ACM/Baltzer Mobile Networks and Applications, vol. 1, no. 2, October 1996, pp. 199-219.

[2] S. Agarwal, A. Ahuja, J.P. Singh, and R. Shorey, \Route-Lifetime Assess- ment Based Routing (RABR) Protocol for Mobile Ad-Hoc Networks," Proceedings of the IEEE International Conference on Communications (ICC), New Orleans, LA, June 2000, pp. 1697-1701.

[3] G. Aggelou and R. Tafazolli, \RDMAR: A Bandwidth-Efficient Routing Protocol for Mobile Ad Hoc Networks," Proceedings of the ACM Inter- national Workshop on Wireless Mobile Multimedia (WoWMoM), Seattle, WA, August 1999, pp. 26-33.

[4] P. Agrawal, D.K. Anvekar, and B. Narendran, \Optimal Prioritization of Handovers in Mobile Cellular Networks," Proceedings of the IEEE International Symposium on Personal, Indoor and Mobile Radio Communication (PIMRC), The Hague, Netherlands, September 1994, pp. 1393-1398.

[5] I.F. Akyildiz, W. Yen, and B. Yener, \A New Hierarchical Routing Proto- cols for Dynamic Multihop Wireless Networks," Proceeding of the IEEE Conference on Computer Communications (INFOCOM), Kobe, Japan April 1997, pp. 1422-1429.

[6] V. Aravamudhan, K. Ratnam, and S. Rangarajan, \An Efficient Multicast Protocol for PCS Networks," ACM/Baltzer Mobile Networks and Applications, vol. 2, no. 4, January 1998, pp. 333-344.

[7] S. Bae, S.-J. Lee, and M. Gerla, \Unicast Performance Analysis of the ODMRP in a Mobile Ad hoc Network Testbed," Proceedings of the IEEE International Conference on Communications and Networks (ICCCN), Las Vegas, October 2000, to appear.

[8] S. Bae, S.-J. Lee, W. Su, and M. Gerla, \The Design, Implementation, and Performance Evaluation of On-Demand Multicast Routing Protocol in Multihop Wireless Networks," IEEE Network, special issue on Multicasting Empowering the Next Generation Internet, vol. 14, no. 1, January/February 2000, pp. 70-77.

[9] S. Bae, S.-J. Lee, W. Su, and M. Gerla, \Implementation of a Multicast Routing Protocol in a Wireless Ad hoc Network Testbed," Technical Re

[10] R. Bagrodia, R. Meyer, M. Takai, Y. Chen, X. Zeng, J. Martin, and H.Y. Song, \PARSEC: A Parallel Simulation Environment for Complex Systems," IEEE Computer, vol. 31, no. 10, October 1998, pp.77-85.

[11] T. Ballardie, P. Francis, and J. Crowcroft, \Core Based Trees (CBT) – An Architecture for Scalable Inter-Domain Multicast Routing," Proceedings of the ACM SIGCOMM Symposium on Communications Architectures, Protocols and Applications, San Francisco, CA, October 1993, pp. 85-95.

[12] A. Bartoli, \Group-Based Multicast and Dynamic Membership in Wireless Networks with Incomplete Spatial Coverage," ACM/Baltzer Mobile Net- works and Applications, vol. 3, no. 2, August 1998, pp. 175-188.

[13] S. Basagni, \Distributed Clustering for Ad Hoc Networks," Proceedings of the IEEE International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN), Perth, Western Australia, June 1999, pp. 310-315.

[14] S. Basagni, I. Chlamtac, V.R. Syrotiuk, and B.A. Woodward, \A Distance Routing Effect Algorithm for Mobility (DREAM)," Proceedings of the ACM/IEEE International Conference on Mobile Computing and Net-working (MOBICOM), Dallas, TX, October 1998, pp. 76-84.

[15] R.E. Bellman, Dynamic Programming, Princeton University Press, Prince- ton, NJ, 1957

Received on 22.10.2011 Accepted on 11.12.2011

Int. J. Tech. 1(2): July-Dec. 2011; Page 130-136